package 动态规划;

public class NC19子数组的最大累加和 {

    /**
     * 给定一个数组arr，返回子数组的最大累加和
     * 例如，arr = [1, -2, 3, 5, -2, 6, -1]，所有子数组中，[3, 5, -2, 6]可以累加出最大的和12，所以返回12.
     * 题目保证没有全为负数的数据
     * [要求]
     * 时间复杂度为O(n)O(n)，空间复杂度为O(1)O(1)
     */

    public int maxsumofSubarray (int[] arr) {

        if(arr.length<1){
            return 0;
        }

        int[] dp=new int[arr.length];
        dp[0]=arr[0];
        int maxResult=dp[0];

        for (int i = 1; i < arr.length; i++) {
            dp[i]=Math.max(dp[i-1]+arr[i],arr[i]);
            maxResult=Math.max(maxResult,dp[i]);
        }

        return dp[arr.length-1];
    }

}
